package org.cabbage.lintcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 最小子串覆盖
 * 给定一个字符串source和一个目标字符串target，在字符串source中找到包括所有目标字符串字母的子串。
 *
 * @author Administrator
 */
public class MinWindow {

    public static void main(String[] args) {
        MinWindow mw = new MinWindow();
        System.out.println(mw.minWindow("abcdbbb", "bcb"));
    }

    public String minWindow(String source, String target) {
        List<Character> list = new ArrayList<Character>();
        List<Character> list2 = new ArrayList<Character>();
        char[] chars = target.toCharArray();
        for (Character c : chars) {
            list.add(c);
            list2.add(c);
        }

        Integer start = null;
        Integer end = null;

        for (int i = 0; i < source.length(); i++) {
            Character c = source.charAt(i);
            if (list.contains(c)) {
                if (start == null) {
                    start = i;
                }
                list.remove(c);
            }
            if (list.size() == 0) {
                end = i;
                break;
            }
        }
        if (start == null || end == null) {
            return "";
        }
        source = source.substring(start, end + 1);
        start = null;
        end = null;
        for (int i = source.length() - 1; i >= 0; i--) {
            Character c = source.charAt(i);
            if (list2.contains(c)) {
                if (end == null) {
                    end = i;
                }
                list2.remove(c);
            }
            if (list2.size() == 0) {
                start = i;
                break;
            }
        }
        if (start == null || end == null) {
            return "";
        }

        return source.substring(start, end + 1);
    }


}
